package com.markus.code.二叉树.study;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/30 22:34
 * todo: 对称二叉树
 */
public class SymmetricTree {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        TreeNode l = root.left;
        TreeNode r = root.right;
        while(l!=null || r!=null || !s1.isEmpty() || !s2.isEmpty()){
            //必须l和r同时不为空才能进行入栈
            while(l!=null && r!=null){
                s1.push(l);l = l.left;
                s2.push(r);r = r.right;
            }
            //来到这个位置说l、r中至少有一个节点为空
            //同级对称的两个位置的节点只要有一个不为空就说明不对称
            if (l != null || r != null){
                return false;
            }
            //此时 l、r都为空
            l = s1.pop();
            r = s2.pop();
            if (l.val != r.val){
                return false;
            }
            l = l.right;
            r = r.left;
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(2);
        SymmetricTree demo = new SymmetricTree();
        System.out.println(demo.isSymmetric(root));
    }
}
